In [21]:
import itertools as it
import time
In [22]:
def imright(h1, h2):
"""Return if h2 is right next to h1."""
return h2-h1 == 1
def nextto(h1, h2):
"""Return if h1 and h2 is next to each other."""
return abs(h2-h1) == 1
def zebra_puzzle():
"""Return a tuple (WATER, ZEBRA) indicating their houses numbers."""
houses = first, _, middle, _, _ = range(1,6)
orderings = list(it.permutations(houses))
return next((WATER, ZEBRA)
for (red, green, ivory, yellow, blue) in orderings
if imright(green, ivory)
for (Englishman, Spaniard, Ukranian, Japanese, Norwegian) in orderings
if Englishman is red
if Norwegian is first
if nextto(Norwegian, blue)
for (dog, snails, fox, horse, ZEBRA) in orderings
if Spaniard is dog
for (coffee, tea, milk, oj, WATER) in orderings
if coffee is green
if Ukranian is tea
if milk is middle
for (OldGold, Kools, Chesterfields, LuckyStrike, Parliaments) in orderings
if OldGold is snails
if Kools is yellow
if nextto(Chesterfields, fox)
if nextto(Kools, horse)
if LuckyStrike is oj
if Japanese is Parliaments
)
def timedcall(fn, *args):
"""Call function with args; return the time in seconds and result"""
t0 = time.clock()
result = fn(*args)
t1 = time.clock()
return t1-t0, result
print "Computation Time:{0} (Water, Zebra):{1}".format(*timedcall(zebra_puzzle))
In [23]:
def ints(start, end = None):
"""Generate integers in the order start, start+1, ... end if end is not None;
Otherwise keep generating."""
i = start
while i <= end or end is None:
yield i
i += 1
def all_ints():
"""Generate integers in the order 0, +1, -1, +2, -2, +3, -3, ..."""
yield 0
for v in ints(1):
yield +v
yield -v
test_fn = all_ints()
assert [test_fn.next() for _ in xrange(5)] == [0, 1, -1, 2, -2]
In [24]:
def average(numbers):
"""Return the average (arithmetic mean) of a sequence of numbers."""
return sum(numbers) / float(len(numbers))
def timedcalls(n, fn, *args):
"""Call fn(*args) repeatedly: n times if n is an int, or up to
n seconds if n is a float; return the min, avg, and max time"""
if isinstance(n, int):
times = [timedcall(fn, *args)[0] for _ in xrange(n)]
else:
times = []
while sum(times) <= n:
times.append(timedcall(fn, *args)[0])
return min(times), average(times), max(times)
print "It takes around {1:.3f} seconds to find the answer.".format(*timedcalls(10, zebra_puzzle))
In [25]:
def c(sequence):
"""Generate items in sequence. c.start is the number of sequences start.
c.count is the number of items generated."""
c.start += 1
for item in sequence:
c.count += 1
yield item
def zebra_puzzle():
"""Return a tuple (WATER, ZEBRA) indicating their houses numbers."""
houses = first, _, middle, _, _ = range(1,6)
orderings = list(it.permutations(houses))
return next((WATER, ZEBRA)
for (red, green, ivory, yellow, blue) in c(orderings)
if imright(green, ivory)
for (Englishman, Spaniard, Ukranian, Japanese, Norwegian) in c(orderings)
if Englishman is red
if Norwegian is first
if nextto(Norwegian, blue)
for (dog, snails, fox, horse, ZEBRA) in c(orderings)
if Spaniard is dog
for (coffee, tea, milk, oj, WATER) in c(orderings)
if coffee is green
if Ukranian is tea
if milk is middle
for (OldGold, Kools, Chesterfields, LuckyStrike, Parliaments) in c(orderings)
if OldGold is snails
if Kools is yellow
if nextto(Chesterfields, fox)
if nextto(Kools, horse)
if LuckyStrike is oj
if Japanese is Parliaments
)
def instrument_fn(fn, *args):
c.start, c.count = 0, 0
result = fn(*args)
print "{} got {} with {:5d} iters over {:7d} items.".format(fn.__name__, result, c.start, c.count)
instrument_fn(zebra_puzzle)
In [13]:
import string, re, itertools
def solve(formula):
"""Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.
Input formula is a string; output is a digit-filled-in string or None."""
for f in fill_in(formula):
if valid(f):
return f
def fill_in(formula):
"Generate all possible fillings-in of letters in formula with digits."
letters = ''.join(set(re.findall('[A-Z]', formula)))
for digits in itertools.permutations('1234567890', len(letters)):
table = string.maketrans(letters, ''.join(digits))
yield formula.translate(table)
def valid(f):
"""Formula f is valid if and only if it has no
numbers with leading zero, and evals true."""
try:
return not re.search(r'\b0[0-9]', f) and eval(f) is True
except ArithmeticError:
return False
def test():
examples = """ODD + ODD == EVEN
A**2 + B**2 == C**2
APPLE + PEN == APPLEPEN"""
for example in examples.strip().split("\n"):
print solve(example.strip())
test()
In [47]:
import cProfile
cProfile.run("test()")
From the profiling, we could see that 'valid' takes far more time than 'fill_in'. In order to speed the funciton of 'valid', we should compile formula into function instead of using 'eval' too many times. For example, compiling 'YOU == ME*2' into 'lambda Y,M,E,U,O: (U+10\O+100*Y) == (E+10*M)**2'.
In [7]:
def faster_solve(formula):
"""Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.
Input formula is a string; output is a digit-filled-in string or None.
This version precompiles the formula; only one eval per formula."""
f, letters = compile_formula(formula)
for digits in itertools.permutations(range(0,10), len(letters)):
try:
if f(*digits):
table = string.maketrans(letters, ''.join(map(str, digits)))
return formula.translate(table)
except ArithmeticError:
pass
def compile_word(word):
if word.isupper():
terms = [("{}*{}".format(10**i, d))
for (i, d) in enumerate(word[::-1])]
return "({})".format("+".join(terms))
else:
return word
def compile_formula(formula, verbose=False):
"""Compile formula into a function. Also return letters found, as a str, in same order as param of function.
For example, 'YOU == ME**2' returns (lambda Y,M,E,U,O: (U+10\O+100*Y) == (E+10M)*2), 'YMEUO'"""
letters = ''.join(set(re.findall(r'[A-Z]', formula)))
parms = ', '.join(letters)
tokens = map(compile_word, re.split(r'([A-Z]+)', formula))
body = ' '.join(tokens)
f = "lambda {}: {}".format(parms, body)
if verbose: print f
return eval(f), letters
In [18]:
def test():
examples = """ODD + ODD == EVEN
A**2 + B**2 == C**2
APPLE + PEN == APPLEPEN"""
for example in examples.strip().split("\n"):
print faster_solve(example.strip())
test()
In [19]:
import cProfile
cProfile.run("test()")
In [20]:
def faster_solve(formula):
"""Given a formula like 'ODD + ODD == EVEN', fill in digits to solve it.
Input formula is a string; output is a digit-filled-in string or None.
This version precompiles the formula; only one eval per formula."""
f, letters = compile_formula(formula)
for digits in itertools.permutations(range(0,10), len(letters)):
try:
if f(*digits):
table = string.maketrans(letters, ''.join(map(str, digits)))
return formula.translate(table)
except ArithmeticError:
pass
def compile_word(word):
if word.isupper():
terms = [("{}*{}".format(10**i, d))
for (i, d) in enumerate(word[::-1])]
return "({})".format("+".join(terms))
else:
return word
def compile_formula(formula, verbose=False):
"""Compile formula into a function. Also return letters found, as a str, in same order as param of function.
For example, 'YOU == ME**2' returns (lambda Y,M,E,U,O: (U+10\O+100*Y) == (E+10M)*2), 'YMEUO'"""
letters = ''.join(set(re.findall(r'[A-Z]', formula)))
firstletters = set(re.findall(r'\b([A-Z])[A-Z]', formula))
parms = ', '.join(letters)
tokens = map(compile_word, re.split(r'([A-Z]+)', formula))
body = ' '.join(tokens)
if firstletters:
body = "{} and {}".format(" and ".join([L + " != 0" for L in firstletters]), body)
f = "lambda {}: {}".format(parms, body)
if verbose: print f
return eval(f), letters
def test():
assert faster_solve('A + B == BA') == None # should NOT return '1 + 0 == 01'
assert faster_solve('YOU == ME**2') == ('289 == 17**2' or '576 == 24**2' or '841 == 29**2')
assert faster_solve('X / X == X') == '1 / 1 == 1'
return 'tests pass'
test()
Out[20]:
In [31]:
def floor_puzzle():
floors = bottom, _, _, _, top = range(1, 6)
lives = itertools.permutations(floors, 5)
return next([Hopper, Kay, Liskov, Perlis, Ritchie]
for (Hopper, Kay, Liskov, Perlis, Ritchie) in lives
if Hopper is not top
if Kay is not bottom
if Liskov not in [bottom, top]
if Perlis > Kay
if abs(Ritchie-Liskov) is not 1
if abs(Liskov-Kay) is not 1)
print floor_puzzle()
In [59]:
def isPalindrome(text):
text = text.lower()
L = len(text)
if L % 2 == 0:
return text[:L/2] == text[-1:-1+L/2:-1]
else:
return text[:L/2] == text[-1:L/2:-1]
def longest_subpalindrome_slice(text):
"Return (i, j) such that text[i:j] is the longest palindrome in text."
if text == "":
return (0, 0)
else:
L = len(text)
ans, Len = (0, 1), 1
for i in xrange(L):
j = i + Len
while j <= L:
if isPalindrome(text[i:j]) and j - i > Len:
ans = (i, j)
Len = j - i
j += 1
return ans
def test():
L = longest_subpalindrome_slice
assert L('racecar') == (0, 7)
assert L('Racecar') == (0, 7)
assert L('RacecarX') == (0, 7)
assert L('Race carr') == (7, 9)
assert L('') == (0, 0)
assert L('something rac e car going') == (8,21)
assert L('xxxxx') == (0, 5)
assert L('Mad am I ma dam.') == (0, 15)
return 'tests pass'
import cProfile
cProfile.run("test()")
In [60]:
def longest_subpalindrome_slice(text):
"Return (i, j) such that text[i:j] is the longest palindrome in text."
if text == "": return (0, 0)
def length(slice):
a, b = slice
return b-a
candidates = [grow(text, start, end)
for start in range(len(text))
for end in (start, start+1)]
return max(candidates, key=length)
def grow(text, start, end):
"Start with a 0- or 1- length palindrome; try to grow a bigger one."
L = len(text)
while (start > 0 and end < L
and text[start-1].upper() == text[end].upper()):
start -= 1
end += 1
return (start, end)
cProfile.run("test()")
In [ ]: